home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 February / EnigmA AMIGA RUN 04 (1996)(G.R. Edizioni)(IT)[!][issue 1996-02][Skylink CD III].iso / earcd / program / mkdpnd11.lha / MkDepend-1.1 / nodes.c < prev    next >
C/C++ Source or Header  |  1995-09-19  |  11KB  |  478 lines
  1. /*
  2. $VER: nodes:c 1.0 (10-Sep-95) Copyright © by Lars Düning
  3. */
  4.  
  5. /*---------------------------------------------------------------------------
  6. ** Management of the dependency tree and nodes.
  7. **
  8. ** Copyright © 1995  Lars Düning  -  All rights reserved.
  9. ** Permission granted for non-commercial use.
  10. **---------------------------------------------------------------------------
  11. ** Each file (source or include) is associated one node which is kept in
  12. ** a binary search tree with the name as index. Glued to each node is
  13. ** a list of that nodes which files the master nodes includes.
  14. ** Each node contains an extra node pointer the module uses to implement
  15. ** tree-independant lists, namely the TODO list of files still to read
  16. ** and a virtual stack for inorder tree traversals.
  17. *
  18. ** Adding and retrieving the files to analyse is done using the functions
  19. **   nodes_addsource()
  20. **   nodes_depend()
  21. **   nodes_todo()
  22. **
  23. ** The output of the dependency tree is done inorder using
  24. **   nodes_initwalk()
  25. **   nodes_inorder()
  26. **
  27. ** The list of dependencies for one single node is managed using
  28. **   nodes_deplist()
  29. **   nodes_freelist()
  30. **
  31. ** Tree traversal and creation must not be mixed!
  32. **---------------------------------------------------------------------------
  33. ** C: DICE 3.01
  34. **---------------------------------------------------------------------------
  35. ** [lars] Lars Düning; Am Wendenwehr 25; D-38114-Braunschweig;
  36. **                     Germany; Tel. 49-531-345692
  37. **---------------------------------------------------------------------------
  38. ** 10-Sep-95 [lars] v 1.0
  39. ** 10-Sep-95 [lars] current
  40. **---------------------------------------------------------------------------
  41. */
  42.  
  43. #include <assert.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46. #include <stdio.h>
  47. #include "nodes.h"
  48.  
  49. /*-------------------------------------------------------------------------*/
  50.  
  51. /* Types for block allocation of Nodes and NodeRefs.
  52.  * Note that Nodes are never freed.
  53.  */
  54.  
  55. #define NBLOCKSIZE 16
  56.  
  57. typedef struct nodeblock
  58.  {
  59.   struct nodeblock * pNext;               /* Next nodeblock */
  60.   int                iFree;               /* Number of first free node */
  61.   Node               aNodes[NBLOCKSIZE];  /* Block of nodes */
  62.  }
  63. NodeBlock;
  64.  
  65. #define RBLOCKSIZE 16
  66.  
  67. typedef struct refblock
  68.  {
  69.   struct refblock * pNext;              /* Next refblock */
  70.   int               iFree;              /* Number of first free noderef */
  71.   NodeRef           aRefs[NBLOCKSIZE];  /* Block of noderefs */
  72.  }
  73. RefBlock;
  74.  
  75. /*-------------------------------------------------------------------------*/
  76.  
  77. static NodeBlock *pFreeNBlocks = NULL;  /* Nodeblocks */
  78. static RefBlock  *pFreeRBlocks = NULL;  /* Refblocks */
  79. static NodeRef   *pFreeRefs    = NULL;  /* List of free NodeRefs */
  80. static Node      *pTree        = NULL;  /* Dependency tree */
  81. static Node      *pList        = NULL;  /* List of (tree) nodes */
  82.   /* The List is used as TODO list for the files to analyse as well as
  83.    * stack simulation for the tree traversal.
  84.    */
  85.  
  86. /*-------------------------------------------------------------------------*/
  87. static Node *
  88. nodes_newnode (void)
  89.  
  90. /* Allocate a new Node.
  91.  *
  92.  * Result:
  93.  *   Pointer to the new Node, or NULL on error.
  94.  *
  95.  * The memory of the Node is cleared, except for .flags which is set
  96.  * to NODE_NEW.
  97.  */
  98.  
  99. {
  100.   Node * pNode;
  101.  
  102.   if (!pFreeNBlocks || !pFreeNBlocks->iFree)
  103.   {
  104.     NodeBlock * pNewBlock;
  105.     pNewBlock = (NodeBlock *)malloc(sizeof(*pNewBlock));
  106.     if (!pNewBlock)
  107.       return NULL;
  108.     memset(pNewBlock, 0, sizeof(*pNewBlock));
  109.     pNewBlock->iFree = NBLOCKSIZE;
  110.     pNewBlock->pNext = pFreeNBlocks;
  111.     pFreeNBlocks = pNewBlock;
  112.   }
  113.   pNode = &(pFreeNBlocks->aNodes[--pFreeNBlocks->iFree]);
  114.   pNode->flags |= NODE_NEW;
  115.   return pNode;
  116. }
  117.  
  118. /*-------------------------------------------------------------------------*/
  119. static NodeRef *
  120. nodes_newref (void)
  121.  
  122. /* Allocate a new NodeRef.
  123.  *
  124.  * Result:
  125.  *   Pointer to the new NodeRef, or NULL on error.
  126.  *
  127.  * The memory of the NodeRef is cleared.
  128.  */
  129.  
  130. {
  131.   NodeRef * pRef;
  132.  
  133.   if (pFreeRefs)
  134.   {
  135.     pRef = pFreeRefs;
  136.     pFreeRefs = pRef->pNext;
  137.   }
  138.   else
  139.   {
  140.     if (!pFreeRBlocks || !pFreeRBlocks->iFree)
  141.     {
  142.       RefBlock * pNewBlock;
  143.       pNewBlock = (RefBlock *)malloc(sizeof(*pNewBlock));
  144.       if (!pNewBlock)
  145.         return NULL;
  146.       pNewBlock->iFree = NBLOCKSIZE;
  147.       pNewBlock->pNext = pFreeRBlocks;
  148.       pFreeRBlocks = pNewBlock;
  149.     }
  150.     pRef = &(pFreeRBlocks->aRefs[--pFreeRBlocks->iFree]);
  151.   }
  152.   memset(pRef, 0, sizeof(*pRef));
  153.   return pRef;
  154. }
  155.  
  156. /*-------------------------------------------------------------------------*/
  157. static void
  158. nodes_freeref (NodeRef * pRef)
  159.  
  160. /* Free a NodeRef.
  161.  *
  162.  *  pRef: Pointer to the NodeRef to free.
  163.  */
  164.  
  165. {
  166.   assert(pRef);
  167.   pRef->pNext = pFreeRefs;
  168.   pFreeRefs = pRef;
  169. }
  170.  
  171. /*-------------------------------------------------------------------------*/
  172. static Node *
  173. nodes_findadd (const char *pName)
  174.  
  175. /* Find the node associated with file *pName. If necessary, add the node.
  176.  *
  177.  *   pName: Pointer to the filename of the node.
  178.  *
  179.  * Result:
  180.  *   Pointer to the node associated with this filename, or NULL on error.
  181.  *
  182.  * If the nodes has been added by this call, NODE_NEW is set in its .flags.
  183.  */
  184.  
  185. {
  186.   Node * pThis, * pPrev;
  187.   int    i;
  188.  
  189.   assert(pName);
  190.   pPrev = NULL;
  191.   if (!pTree)
  192.   {
  193.     pTree = nodes_newnode();
  194.     return pTree;
  195.   }
  196.   pThis = pTree;
  197.   while(pThis)
  198.   {
  199.     i = strcmp(pThis->pName, pName);
  200.     if (!i)
  201.       return pThis;
  202.     pPrev = pThis;
  203.     if (i > 0)
  204.       pThis = pThis->pLeft;
  205.     else
  206.       pThis = pThis->pRight;
  207.   }
  208.   pThis = nodes_newnode();
  209.   if (pThis)
  210.   {
  211.     if (i > 0)
  212.       pPrev->pLeft = pThis;
  213.     else
  214.       pPrev->pRight = pThis;
  215.   }
  216.   return pThis;
  217. }
  218.  
  219. /*-------------------------------------------------------------------------*/
  220. int
  221. nodes_addsource (const char *pName, int bAvoid)
  222.  
  223. /* Add a source file to the dependency tree.
  224.  *
  225.  *   pName : Name of the file to add.
  226.  *   bAvoid: True if the file is explicitely _no_ sourcefile.
  227.  *
  228.  * Result:
  229.  *   0 on success, non-0 on error (out of memory).
  230.  *
  231.  * The file is also added to the internal TODO list of files.
  232.  */
  233.  
  234. {
  235.   Node *pNode;
  236.  
  237.   assert(pName);
  238.   pNode = nodes_findadd(pName);
  239.   if (!pNode)
  240.     return 1;
  241.   if (pNode->flags & NODE_NEW)
  242.   {
  243.     pNode->flags = NODE_SOURCE;
  244.     pNode->pName = strdup(pName);
  245.     if (!pNode->pName)
  246.       return 1;
  247.     if (!bAvoid)
  248.     {
  249.       pNode->pNext = pList;
  250.       pList = pNode;
  251.     }
  252.   }
  253.   if (bAvoid)
  254.     pNode->flags |= NODE_AVOID;
  255.   return 0;
  256. }
  257.  
  258. /*-------------------------------------------------------------------------*/
  259. int
  260. nodes_depend (Node * pDepender, const char * pName)
  261.  
  262. /* Add file *pName to the list of dependees of *pDepender.
  263.  *
  264.  *  pDepender: Node which depends on the file given.
  265.  *  pName    : Name of the file pDepender depends on.
  266.  *
  267.  * Result:
  268.  *   0 on success, non-0 on error (out of memory).
  269.  *
  270.  * The file is added to the dependee-list and is also inserted into the
  271.  * dependency tree and the TODO list to compute nested dependencies.
  272.  */
  273.  
  274. {
  275.   Node    * pNode;
  276.   NodeRef * pRef;
  277.  
  278.   assert(pDepender);
  279.   assert(pName);
  280.  
  281.   pNode = nodes_findadd(pName);
  282.   if (!pNode)
  283.     return 1;
  284.   if (pNode->flags & NODE_NEW)
  285.   {
  286.     pNode->flags = 0;
  287.     pNode->pName = strdup(pName);
  288.     if (!pNode->pName)
  289.       return 1;
  290.     pNode->pNext = pList;
  291.     pList = pNode;
  292.   }
  293.  
  294.   /* Add pNode to pDependers->pDeps if not already there */
  295.   for ( pRef = pDepender->pDeps
  296.       ; pRef && pRef->pNode != pNode
  297.       ; pRef = pRef->pNext
  298.       );
  299.   if (!pRef)
  300.   {
  301.     pRef = nodes_newref();
  302.     if (!pRef)
  303.       return 1;
  304.     pRef->pNode = pNode;
  305.     pRef->pNext = pDepender->pDeps;
  306.     pDepender->pDeps = pRef;
  307.   }
  308.   return 0;
  309. }
  310.  
  311. /*-------------------------------------------------------------------------*/
  312. Node *
  313. nodes_todo (void)
  314.  
  315. /* Return the tree node of the next file to analyse.
  316.  *
  317.  * Result:
  318.  *   Pointer to the node of the next file to analyse, or NULL if there is
  319.  *   none.
  320.  */
  321.  
  322. {
  323.   Node * pNode;
  324.  
  325.   /* NODE_DONE should not happen, but checking it is free */
  326.   while (pList && (pList->flags & (NODE_AVOID|NODE_DONE)))
  327.     pList = pList->pNext;
  328.   if (pList)
  329.   {
  330.     pNode = pList;
  331.     pList = pList->pNext;
  332.     pNode->flags |= NODE_DONE;
  333.   }
  334.   else
  335.     pNode = NULL;
  336.   return pNode;
  337. }
  338.  
  339. /*-------------------------------------------------------------------------*/
  340. void
  341. nodes_initwalk (void)
  342.  
  343. /* Initialise a tree traversal.
  344.  */
  345.  
  346. {
  347.   assert(!pList);
  348.   pList = pTree;
  349.   if (pList)
  350.   {
  351.     pList->iStage = 0;
  352.     pList->pNext = NULL;
  353.   }
  354. }
  355.  
  356. /*-------------------------------------------------------------------------*/
  357. Node *
  358. nodes_inorder (void)
  359.  
  360. /* Return the next Node of an inorder tree traversal.
  361.  *
  362.  * Result:
  363.  *   Pointer to the next node, or NULL if traversal is complete.
  364.  */
  365.  
  366. {
  367.   Node *pNode;
  368.   if (!pList)
  369.     return NULL;
  370.   while (pList)
  371.   {
  372.     switch (pList->iStage)
  373.     {
  374.     case 0:
  375.       pList->iStage++;
  376.       pNode = pList->pLeft;
  377.       break;
  378.     case 1:
  379.       pList->iStage++;
  380.       return pList;
  381.       break;
  382.     case 2:
  383.       pList->iStage++;
  384.       pNode = pList->pRight;
  385.       break;
  386.     case 3:
  387.       pList = pList->pNext;
  388.       pNode = NULL;
  389.       break;
  390.     default:
  391.       assert(0);
  392.       break;
  393.     }
  394.     if (pNode)
  395.     {
  396.       pNode->pNext = pList;
  397.       pList = pNode;
  398.       pNode->iStage = 0;
  399.     }
  400.   }
  401.   return NULL;
  402. }
  403.  
  404. /*-------------------------------------------------------------------------*/
  405. NodeRef *
  406. nodes_deplist (Node * pNode)
  407.  
  408. /* Gather the list of dependees of *pNode.
  409.  *
  410.  * Result:
  411.  *   Pointer to the list of dependees, or NULL if an error occurs.
  412.  *   First entry in the list is pNode itself.
  413.  */
  414.  
  415. {
  416.   NodeRef *pDList;
  417.   NodeRef *pMark;
  418.   NodeRef *pThis;
  419.   NodeRef *pRover;
  420.   Node    *pDep;
  421.  
  422.   assert(pNode);
  423.   pDList = nodes_newref();
  424.   if (!pDList)
  425.     return NULL;
  426.  
  427.   /* The list of dependencies is gathered in a wide search. */
  428.   pDList->pNode = pNode;
  429.   NODES_MARK(pNode);
  430.   for ( pThis = pDList, pMark = pDList
  431.       ; pMark
  432.       ; pMark = pMark->pNext
  433.       )
  434.   {
  435.     for ( pRover = pMark->pNode->pDeps
  436.         ; pRover
  437.         ; pRover = pRover->pNext
  438.         )
  439.     {
  440.       pDep = pRover->pNode;
  441.       if (!NODES_MARKED(pDep))
  442.       {
  443.         pThis->pNext = nodes_newref();
  444.         if (!pThis->pNext)
  445.           return NULL;
  446.         pThis = pThis->pNext;
  447.         pThis->pNode = pDep;
  448.         NODES_MARK(pDep);
  449.       }
  450.     }
  451.   }
  452.   return pDList;
  453. }
  454.  
  455. /*-------------------------------------------------------------------------*/
  456. void
  457. nodes_freelist (NodeRef * pDList)
  458.  
  459. /* Free a dependency list earlier produced by nodes_deplist().
  460.  *
  461.  *   pDList: Base of the list to free.
  462.  */
  463.  
  464. {
  465.   NodeRef * pThis;
  466.  
  467.   while (pDList)
  468.   {
  469.     NODES_UNMARK(pDList->pNode);
  470.     pThis = pDList;
  471.     pDList = pDList->pNext;
  472.     pThis->pNext = pFreeRefs;
  473.     pFreeRefs = pThis;
  474.   }
  475. }
  476.  
  477. /***************************************************************************/
  478.